#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ysh's method
    // int maxProfit(vector<int> &prices)
    // {
    //     prices.insert(prices.begin(), INT_MAX);
    //     prices.push_back(INT_MIN);
    //     int max_profit = 0;
    //     int buy_index = 0;
    //     int sold_index = 0;
    //     for (size_t i = 1; i < prices.size() - 1; i++)
    //     {
    //         if (prices[i] <= prices[i - 1] && prices[i] < prices[i + 1])
    //         {
    //             if (buy_index != 0 && prices[i] > prices[buy_index])
    //             {
    //                 continue;
    //             }
    //             buy_index = i;
    //             //cout << "buy" << buy_index << endl;
    //         }
    //         if (prices[i] >= prices[i - 1] && prices[i] > prices[i + 1])
    //         {
    //             if (buy_index != 0)
    //             {
    //                 sold_index = i;
    //                 //cout << "sold" << sold_index << endl;
    //                 max_profit += prices[sold_index] - prices[buy_index];
    //                 buy_index = 0;
    //             }
    //         }
    //     }
    //     return max_profit;
    // }

    // book's greedy_algorithm
    // int maxProfit(vector<int> &prices)
    // {
    //     int result = 0;
    //     for (size_t i = 1; i < prices.size(); i++)
    //     {
    //         result += max(prices[i] - prices[i - 1], 0);
    //     }
    //     return result;
    // }

    // dynamic_planning
    int maxProfit(vector<int> &prices)
    {
        size_t size = prices.size();
        vector<vector<int>> dp(size, vector<int>(2, 0));
        dp[0][0] = dp[0][0] - prices[0];
        for (size_t i = 1; i < prices.size(); i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i][0] + prices[i]);
        }
        return max(dp[size - 1][0], dp[size - 1][1]);
    }
};

int main()
{
    vector<int> prices{0, 5, 5, 6, 2, 1, 1, 3};
    Solution sol;
    cout << sol.maxProfit(prices) << endl;
    return 0;
}